// Created by WXX on 2021/9/9 10:03
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
 * 内存消耗：7.2 MB, 在所有 C++ 提交中击败了54.74%的用户
 */
class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int maxWidth) {

        int n = words.size();

        vector<string> res;
        for (int i = 0; i < n; i++) {
            int j = i + 1, sum = words[i].size();
            while (j < n && sum + words[j].size() + j - i <= maxWidth) {
                sum += words[j++].size();
            }
            int cnt = j - i;  // cnt个单词，cnt-1个间距
            if (cnt == 1) res.push_back(words[i] + string(maxWidth - words[i].size(), ' '));
            else {
                if (j != n) {
                    int d = (maxWidth - sum + cnt - 2) / (cnt - 1);  // 间距
                    int num = 1;  // 间距可以是d的间距的数量
                    while (d * (num + 1) + (d - 1) * (cnt - 1 - num - 1) <= maxWidth - sum) num++;

                    string s = words[i];
                    for (int k = i + 1, u = 0; k < j; k++, u++) {
                        if (u < num) s += string(d, ' ');
                        else s += string(d - 1, ' ');
                        s += words[k];
                    }
                    res.push_back(s);
                } else {  // 最后一行间隔为1
                    string s = words[i];
                    for (int k = i + 1; k < j; k++) s += ' ' + words[k];
                    s += string(maxWidth - sum - (cnt - 1), ' ');
                    res.push_back(s);
                }
            }
            i = j - 1;
        }
        return res;
    }
};

void OutputBasicArray1D(const vector<string>& nums) {
    cout << "[" << endl;
    for (const auto & num : nums)
        cout << "   \"" << num << "\"," << endl;
    cout << "]" << endl;
}

int main() {

    vector<string> words = {"This", "is", "an", "example", "of", "text", "justification."};
    OutputBasicArray1D(Solution().fullJustify(words, 16));

    return 0;
}
